% small.tex
\documentclass{beamer}
\usetheme{Copenhagen}

\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{cancel}
\usepackage{umoline}
\usepackage{ulem}
\usepackage{lmodern}

\title{Clustering}
\author{Carlos Colmenares \and Kelwin Fernández}
\institute[UMBC]{
  Universidad Simón Bolívar, Sartenejas\\
  Diseño de Algoritmos II - CI5652\\[1ex]

}
\date{Junio, 2011}

\begin{document}

%--- the titlepage frame -------------------------%
\begin{frame}[plain]
  \titlepage
\end{frame}

\begin{frame}{Programa}
\tableofcontents
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Definición}

\begin{frame}{Definición}

\begin{block}{Definición Informal}
El problema de clustering consiste en realizar una partición de un
conjunto, cuyos elementos son observaciones de algún tipo, de tal manera que los elementos en cada subconjunto
de la partición se asemejen unos a otros de cierta manera, mientras que los elementos
en subconjuntos distintos deben parecerse lo menos posible.
\end{block}
\end{frame}

\section{Metaheurísticas Implementadas}

\begin{frame}{Metaheurísticas Implementadas}
\begin{itemize}
\item AntClust Algorithm.
\item AntClust Hybrid Algorithm.
\end{itemize}
\end{frame}

\begin{frame}{AntClust Algorithm (ACA)}

\begin{itemize}
\item Cada dato se encuentra individualmente en un
grupo diferente.
\item Cada hormiga selecciona un
dato libre y retorna a su hormiguero.
\item Durante un proceso iterativo, una hormiga es
seleccionada aleatoriamente, desarrolla un número
de movimientos entre su hormiguero y el espacio donde
se encuentran los datos y decide probabilísticamente
si soltar o no el dato. Si la hormiga se vuelve libre (no está
cargando ningún dato) busca un nuevo dato que cargar.
\end{itemize}

\end{frame}

\begin{frame}{AntClust Algorithm (ACA)}

Medida de similitud del dato $p_i$ con el cluster $c_k$:


$$ f(p_i, c_k) = \dfrac{1}{n_k} \Sigma_{p_j \in c_k}
		\dfrac{\alpha^2}{\alpha^2 + d(p_i,p_j)^2}$$

donde

$$ \alpha = \dfrac{1}{N(N-1)} \Sigma_{1\leq i,j \leq N} d(p_i,p_j)$$
\end{frame}

\begin{frame}{AntClust Algorithm (ACA)}
Adicionalmente la probabilidad de agarrar un dato viene dada por:

\bigskip
$$p_{pick}(p_i,c_k) =
	\begin{cases}
		1, & \mbox{si } |c_k|\mbox{ = 1} \\
		q, & \mbox{si } |c_k|\mbox{ = 2} \\
		cos^2 \left( \dfrac{\pi}{2}f(p_i,c_k) \right) &  \mbox{en otro caso}\\
    \end{cases}
$$

donde $q$ es una constante entre 0 y 1 regularmente alta.

Y la probabilidad de liberarlo viene dada por:

\bigskip
$$p_{drop}(p_i,c_k) =
		1 - cos^2 \left( \dfrac{\pi}{2}f(p_i,c_k) \right)\\
$$

\end{frame}

\begin{frame}{AntClust Algorithm (ACA)}
\texttt{
\hspace{-0.35cm}
( 1) proc ACA():\\
( 2) \hspace{0.2cm}    asignarDatosIndividualmente()\\
( 2)     \\
( 3) \hspace{0.2cm}    Para cada hormiga a(i):\\
( 4) \hspace{0.4cm}       seleccionarDatoLibre(a(i))\\
( 5) \hspace{0.4cm}       volverColonia(a(i))\\
( 6)     \\
( 7) \hspace{0.2cm}    procesoIterativo()\\
( 8)     \\
( 9) \hspace{0.2cm}    S <- transformarProblema()\\
(10) \hspace{0.2cm}    mientras !puntoFijo:\\
(11) \hspace{0.4cm}        S <- filtrado(S)\\
(12) \hspace{0.4cm}        S <- kMeans(S)\\
}
\end{frame}

\begin{frame}{AntClust Algorithm (ACA)}
\texttt{
\hspace{-0.35cm}
( 1) proc procesoIterativo():\\
( 2) \hspace{0.2cm}    mientras !criterioParada:\\
( 2) \hspace{0.2cm}        Para cada hormiga:\\
( 3) \hspace{0.4cm}            a(i) = hormiga seleccionada aleatoriamente\\
( 4) \hspace{0.4cm}            Si a(i) carga dato(i) entonces:\\
( 5) \hspace{0.6cm}                c(k) = cluster selecto aleatoriamente\\
( 6) \hspace{0.6cm}                Si ( random <= Pdrop( dato(i), c(k) ):\\
( 7) \hspace{1.0cm}                    mover a(i) a c(k) y soltar dato(i)\\
( 8) \hspace{0.6cm}            Sino:\\
( 9) \hspace{0.8cm}                dato(i) = dato libre selec aleatoriamente\
(10) \hspace{0.8cm}                c(k) = cluster donde esta dato(i)\\
(11) \hspace{0.8cm}                Si ( random <= Ppick( dato(i), c(k) ):\\
(12) \hspace{1.0cm}                    mover a(i) a c(k) y agarrar dato(i)\\
(13) \hspace{0.2cm}        Mover a(i) al hormiguero\\
}
\end{frame}

\begin{frame}{AntClust Hybrid Algorithm (ACHA)}
\texttt{
\hspace{-0.35cm}
( 1) proc ACHA():\\
( 2) \hspace{0.2cm}    S <- ACA()\\
( 2) \hspace{0.2cm}    S <- ILS(S)\\
( 3)     \\
( 4) \hspace{0.2cm}    mientras !puntoFijo:\\
( 5) \hspace{0.4cm}        S <- filtrado(S)\\
( 6) \hspace{0.2cm}        S <- kMeans(S)\\
}
\end{frame}

\section{Resultados Globales}

\begin{frame}{Iris, Wine, Ecoli}
\begin{scriptsize}
\hspace*{-0.5cm}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{8}{|c|}{\textbf{Iris}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & \textbf{0.2545} & \textbf{0.1143} & \textbf{0.1762} & 4.1975 & \textbf{10} & \textbf{3} & 6.7\\
\hline
ACHA & \textbf{0.2545} & 0.1181 & 0.1964 & 5.4723 & \textbf{10} & \textbf{3} & \textbf{5.03}\\
\hline
\multicolumn{8}{|c|}{\textbf{Wine}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & \textbf{0.2549} & \textbf{0.1244} & \textbf{0.1734} & 4.3743 & \textbf{13} & \textbf{8} & 11.07\\
\hline
ACHA & 0.2256 & 0.1344 & 0.1735 & 17.2653 & \textbf{13} & \textbf{8} & \textbf{10.83}\\
\hline
\multicolumn{8}{|c|}{\textbf{Ecoli}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & 0.0921 & \textbf{0.0601} & 0.07773 & 4.2162 & 26 & 19 & 20.87\\
\hline
ACHA & \textbf{0.0899} & \textbf{0.0601} & \textbf{0.0729} & 24.5656 &  \textbf{23} & \textbf{17} & \textbf{20.8}\\
\hline
\end{tabular}
\end{scriptsize}
\end{frame}

\begin{frame}{Círculos 1,2,3}
\begin{scriptsize}
\hspace*{-0.5cm}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{8}{|c|}{\textbf{Círculos 1}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & \textbf{0.2066} & \textbf{0.1023} & \textbf{0.1478} & 4.2262 & 10 & \textbf{3} & 5.9\\
\hline
ACHA & 0.2292 & 0.1181 & 0.1523 & 8.1231 & \textbf{7} & \textbf{3} & \textbf{4.2}\\
\hline
\multicolumn{8}{|c|}{\textbf{Círculos 2}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & 0.2924 & 0.0797 & 0.1382 & 4.3815 & 14 & 4 & 7.13\\
\hline
ACHA & \textbf{0.2423} & \textbf{0.0753} & \textbf{0.1334} & 10.1122 & \textbf{11} & \textbf{3} & \textbf{6.1}\\
\hline
\multicolumn{8}{|c|}{\textbf{Círculos 3}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & 0.1954 & 0.0746 & 0.1149 & 4.4118 & \textbf{12} & \textbf{4} & 7.15\\
\hline
ACHA & \textbf{0.1852} & \textbf{0.0605} & \textbf{0.1146} & 10.95 & 14 & \textbf{4} & \textbf{6.67}\\
\hline
\end{tabular}
\end{scriptsize}
\end{frame}

\begin{frame}{Círculos 4,5,6}
\begin{scriptsize}
\hspace*{-0.5cm}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{8}{|c|}{\textbf{Círculos 4}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & \textbf{0.209} & \textbf{0.063} & \textbf{0.1237} & 4.473 & 10 & 4 & 6.57\\
\hline
ACHA & 0.3292 & \textbf{0.063} & 0.1276 & 12.0905 & \textbf{8} & \textbf{3} & \textbf{5.37}\\
\hline
\multicolumn{8}{|c|}{\textbf{Círculos 5}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & 0.0818 & 0.0292 & 0.0394 & 5.7047 & \textbf{34} & \textbf{13} & 26.73\\
\hline
ACHA & \textbf{0.0774} & \textbf{0.0202} & \textbf{0.0387} & 44.36 & 51 & \textbf{13} & \textbf{26.87}\\
\hline
\multicolumn{8}{|c|}{\textbf{Círculos 6}}\\
\hline
 & Peor & Mejor & Prom & T$_{prom}(seg)$ & \#Clu$_{peor}$ & \#Clu$_{mejor}$ & \#Clu$_{prom}$\\
\hline
ACA & \textbf{0.0777} & 0.0293 & \textbf{0.0468} & 5.528 & \textbf{34} & 13 & 24.97\\
\hline
ACHA & 0.0894 & \textbf{0.0292} & 0.0494 & 40.3574 & 35 & \textbf{12} & \textbf{22.73}\\
\hline
\end{tabular}
\end{scriptsize}
\end{frame}

\section{Resultados Gráficos}

\begin{frame}{AntClust Algorithm}
\begin{center}
\includegraphics[scale=0.2]{ACA/s1/ACA4.jpg}
\end{center}
\end{frame}

\begin{frame}{AntClust Algorithm}
\begin{center}
\includegraphics[scale=0.2]{ACA/s1/ACA4sol.jpg}
\end{center}
\end{frame}

\begin{frame}{AntClust Algorithm}
\begin{center}
\includegraphics[scale=0.2]{ACA/s2/ACA4.jpg}
\end{center}
\end{frame}

\begin{frame}{AntClust Algorithm}
\begin{center}
\includegraphics[scale=0.2]{ACA/s2/ACA4sol.jpg}
\end{center}
\end{frame}

\begin{frame}{AntClust Algorithm}
\begin{center}
\includegraphics[scale=0.2]{ACA/s3/ACA4.jpg}
\end{center}
\end{frame}

\begin{frame}{AntClust Algorithm}
\begin{center}
\includegraphics[scale=0.2]{ACA/s3/ACA4sol.jpg}
\end{center}
\end{frame}

\begin{frame}{AntClust Hybrid Algorithm}
\begin{center}
\includegraphics[scale=0.2]{ACHA/s1/ACHA4.jpg}
\end{center}
\end{frame}

\begin{frame}{AntClust Hybrid Algorithm}
\begin{center}
\includegraphics[scale=0.2]{ACHA/s1/ACHA4sol.jpg}
\end{center}
\end{frame}

\begin{frame}{AntClust Hybrid Algorithm}
\begin{center}
\includegraphics[scale=0.2]{ACHA/s2/ACHA7.jpg}
\end{center}
\end{frame}

\begin{frame}{AntClust Hybrid Algorithm}
\begin{center}
\includegraphics[scale=0.2]{ACHA/s2/ACHA7sol.jpg}
\end{center}
\end{frame}

\begin{frame}{AntClust Hybrid Algorithm}
\begin{center}
\includegraphics[scale=0.2]{ACHA/s3/ACHA7.jpg}
\end{center}
\end{frame}

\begin{frame}{AntClust Hybrid Algorithm}
\begin{center}
\includegraphics[scale=0.2]{ACHA/s3/ACHA7sol.jpg}
\end{center}
\end{frame}
\end{document}